// 无向图的基本实现
// 这里采用了邻接表来表示图

import { Adjacencylist, WalkGraph } from './type';

export class NonDirectGraph<T = unknown>{
    protected vertexes: T[];// 顶点集合
    protected adjList: Adjacencylist<T>;// 邻接表
    protected defaultCallback: VoidValueCallback<T>;// 默认回调函数
    // 构造函数
    constructor() {
        this.vertexes = [];
        this.adjList = new Map<T, T[]>();
        this.defaultCallback = (value: T) => console.dir(value);
    }
    get [Symbol.toStringTag]() {
        return 'NonDirectGraph';
    }
    // 顶点集合不存在提示
    protected warnVertexNotExist(vertex: T): void {
        console.warn(`${vertex} 不存在与顶点集合中，请先调用addVertex()方法`);
    }
    // 遍历图通用方法
    protected walkGraph(isDfs: boolean, start: T, callback: VoidValueCallback<T>): void {
        // 检查起点是否存在
        if (!this.hasVertex(start)) {
            console.trace();
            console.warn(`不存在的遍历起点：${start}`);
            return;
        }
        const visited = new Set<T>();
        const walk: WalkGraph<T> = isDfs ? this.dfsWalk : this.bfsWalk;
        walk.call(this, start, visited, callback);// 记住绑定this
    }
    // DFS内置遍历方法
    protected dfsWalk(start: T, visited: Set<T>, callback: VoidValueCallback<T>): void {
        callback(start);
        visited.add(start);// 标记访问
        const neighbours = this.adjList.get(start) || [];
        for (let i = 0; i < neighbours.length; i++) {
            // 如果当前节点未访问过，就调用深度优先遍历
            if (!visited.has(neighbours[i])) {
                this.dfsWalk(neighbours[i], visited, callback);
            }
        }
    }
    // BFS内置遍历方法
    protected bfsWalk(start: T, visited: Set<T>, callback: VoidValueCallback<T>): void {
        const queue: T[] = [start];// 访问队列
        visited.add(start);
        while (queue.length > 0) {
            const currVertex = queue.shift()!;
            const neighbours = this.adjList.get(currVertex) || [];
            for (let i = 0; i < neighbours.length; i++) {
                // 如果没有访问过就加入队列中
                if (!visited.has(neighbours[i])) {
                    queue.push(neighbours[i]);
                    visited.add(neighbours[i]);
                }
            }
            // 访问完当前层次调用回调函数
            callback(currVertex);
        }
    }
    // 添加顶点
    addVertex(vertex: T): boolean {
        // 如果当前顶点为存在于顶点集合中，则添加更新
        if (!this.vertexes.includes(vertex)) {
            this.vertexes.push(vertex);
            this.adjList.set(vertex, []);
            return true;
        }
        return false;
    }
    // 判断是否存在顶点
    hasVertex(vertex: T): boolean {
        return this.vertexes.includes(vertex);
    }
    // 添加连通分量
    addConnection(vertex1: T, vertex2: T): boolean {
        if (vertex1 === vertex2) {
            throw new RangeError('输入参数形成了自连通路，请检查输入');
        }
        // 首先需要保证两个顶点均在集合中
        if (!this.vertexes.includes(vertex1)) {
            this.warnVertexNotExist(vertex1);
            return false;
        }
        if (!this.vertexes.includes(vertex2)) {
            this.warnVertexNotExist(vertex2);
            return false;
        }
        // 再分别更新连通分量
        this.adjList.get(vertex1)?.push(vertex2);
        this.adjList.get(vertex2)?.push(vertex1);
        return true;
    }
    // 输出无向图
    show(): void {
        this.vertexes.forEach((v) => {
            const list = this.adjList.get(v) || [];
            let output = '';
            list.forEach((oV) => {
                output += `${oV} `
            });
            console.log(`${v} --->  ${output}`);
        });
    }
    // 深度优先遍历
    dfs(start: T, callback: VoidValueCallback<T> = this.defaultCallback): void {
        this.walkGraph(true, start, callback);
    }
    // 广度优先遍历
    bfs(start: T, callback: VoidValueCallback<T> = this.defaultCallback): void {
        this.walkGraph(false, start, callback);
    }
    // 求最短路径
    getMinDistance(vertex1: T, vertex2: T): number {
        // 首先需要保证两个顶点均在集合中
        if (!this.vertexes.includes(vertex1)) {
            this.warnVertexNotExist(vertex1);
            return -1;
        }
        if (!this.vertexes.includes(vertex2)) {
            this.warnVertexNotExist(vertex2);
            return -1;
        }
        const queue: T[] = [vertex1];// 访问队列
        const visited = new Set<T>(queue);
        let step = 0;// 步长
        while (queue.length > 0) {
            const currLen = queue.length;// 当前层级长度
            for (let i = 0; i < currLen; i++) {
                const currVertex = queue.shift()!;
                const neighbours = this.adjList.get(currVertex) || [];
                // 如果找到节点则直接返回步长
                if (currVertex === vertex2) {
                    return step;
                }
                // 否则继续广度优先遍历
                for (let i = 0; i < neighbours.length; i++) {
                    // 如果没有访问过就加入队列中
                    if (!visited.has(neighbours[i])) {
                        queue.push(neighbours[i]);
                        visited.add(neighbours[i]);
                    }
                }
            }
            step++;// 更新步长
        }
        return -1;// 没有找到则返回-1
    }
}

